﻿#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
	// 查找x是否在树中
	bool IsInTree(TreeNode* root, TreeNode* x)
	{
		if (root == nullptr)
			return false;
		return root == x
			|| IsInTree(root->left, x)
			|| IsInTree(root->right, x);
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL)
			return NULL;
		if (root == p || root == q)
		{
			return root;
		}
		// 这⾥要注意，这⾥的命名⾮常关键，命名好了，代码可读性⼤⼤增强
		bool pInLeft, pInRight, qInLeft, qInRight;
		// 题⽬中有说明p和q⼀定是树中的结点
		// p不在左树就在右树
		pInLeft = IsInTree(root->left, p);
		pInRight = !pInLeft;
		// q不在左树就在右树
		qInLeft = IsInTree(root->left, q);
		qInRight = !qInLeft;
		// ⼀个在左，⼀个在右，那么root就是最近公共祖先
		// 都在左，递归去左树查找
		// 都在右，递归去右树查找
		if ((pInLeft && qInRight) || (qInLeft && pInRight))
		{
			return root;
		}
		else if (pInLeft && qInLeft)
		{
			return lowestCommonAncestor(root->left, p, q);
		}
		else if (pInRight && qInRight)
		{
			return lowestCommonAncestor(root->right, p, q);
		}
		// 虽然执⾏逻辑不会⾛到这⾥，但是如果不写这个代码，语法逻辑过不去(相当于语法上⾛到这没返回值)
		// 编译器会报语法错误。
			
		return NULL;
	}
}